package inset

import (
	"bytes"
	"fmt"
)

/*
    bit数组--实现集合
	1、Go语言里的集合一般会用map[T]bool这种形式来表示，使用bit数组更好的表示它
	2、在数据流分析领域，集合元素通常是一个非负整数，集合会包含很多元素，并且集合会经常进行并集、交集操作
	3、一个bit数组通常会用一个无符号数或者称之为“字”的slice来表示


	功能解析：
	1、一个uint64，会有64个bit，每个bit代表一个元素，每个元素可以是0或者1
	2、所以切片索引0，可以存放0到63的数字。例如0放在第一个bit，1放在第二个bit，2放在第三个bit，以此类推。最终添加0,1,2，会将第0,1,2个bit设置为1，其他的bit设置为0，得到7
*/
type IntSet struct {
	words []uint64
}

// Has 报告该集合是否包含非负值 x。
func (s *IntSet) Has(x int) bool {
	word, bit := x/64, uint(x%64)
	return word < len(s.words) && s.words[word]&(1<<bit) != 0
}

//Add 将非负值 x 添加到集合中。
func (s *IntSet) Add(x int) {
	word, bit := x/64, uint(x%64)
	for word >= len(s.words) {
		s.words = append(s.words, 0)
	}
	s.words[word] |= 1 << bit // |= 是按位或。 << 是左移。
}

// UnionWith 将 s 设置为 s 和 t 的并集。
func (s *IntSet) UnionWith(t *IntSet) {
	for i, tword := range t.words {
		if i < len(s.words) {
			s.words[i] |= tword
		} else {
			s.words = append(s.words, tword)
		}
	}
}

//String 以“{1 2 3}”形式的字符串形式返回集合。
func (s *IntSet) String() string {
	var buf bytes.Buffer
	buf.WriteByte('{')
	for i, word := range s.words {
		if word == 0 {
			continue
		}
		for j := 0; j < 64; j++ {
			if word&(1<<uint(j)) != 0 {
				if buf.Len() > len("{") {
					buf.WriteByte(' ')
				}
				fmt.Fprintf(&buf, "%d", 64*i+j)
			}
		}
	}
	buf.WriteByte('}')
	return buf.String()
}
